package SubjectBacktracking.Four;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class FindItinerary {

/**
 * 难度：中等
 * 
 * 332. 重新安排行程
 * 	给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示
 * 	飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个
 * 	从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
 * 	
 * 提示：
 * 	1.如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。
 * 	例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
 * 	2.所有的机场都用三个大写字母表示（机场代码）。
 * 	3.假定所有机票至少存在一种合理的行程。
 * 	4.所有的机票必须都用一次 且 只能用一次。
 * 	
 * 示例 1：
 * 	输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
 * 	输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
 * 	
 * 示例 2：
 * 	输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 	输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 	解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FindItinerary fi = new FindItinerary();
		List<String> a1 = Arrays.asList("JFK","SFO");
		List<String> a2 = Arrays.asList("JFK","ATL");
		List<String> a3 = Arrays.asList("SFO","ATL");
		List<String> a4 = Arrays.asList("ATL","JFK");
		List<String> a5 = Arrays.asList("ATL","SFO");
		List<List<String>> tickets = new ArrayList<>();
		tickets.add(a1);
		tickets.add(a2);
		tickets.add(a3);
		tickets.add(a4);
		tickets.add(a5);
		System.out.println(fi.findItinerary(tickets));
	}

	//自己写
	List<String> path = new ArrayList<>();
	public List<String> findItinerary(List<List<String>> tickets) {
//		System.out.println(tickets);
		//先对目的地进行排序
		tickets.sort(new Comparator<List<String>>() {

			@Override
			public int compare(List<String> arg0, List<String> arg1) {
				// TODO Auto-generated method stub
//				System.out.println(arg0.get(1)+","+arg1.get(1));
//				System.out.println(arg0.get(1).charAt(0) < arg1.get(1).charAt(0));
				
				return arg0.get(1).compareTo(arg1.get(1));
			}
			
		});
//		System.out.println(tickets);
		// 起始机场
		path.add("JFK");
		backtracking(tickets, new boolean[tickets.size()],"JFK");
		return path;
    }
	public boolean backtracking(List<List<String>> tickets, boolean[] used, String key){
		if(path.size()==tickets.size()+1) {
			return true;
		}
		for(int i=0;i<tickets.size();i++) {
			// 判断是否有该机场,并且该机场是否已经飞过
			if(tickets.get(i).get(0).contains(key) && !used[i]) {
				path.add(tickets.get(i).get(1));
				used[i] = true;// 记录到达机场是否飞过了
				if(backtracking(tickets, used, tickets.get(i).get(1)))return true;
				used[i] = false;
				path.remove(path.size()-1);
			}
		}
		return false;
	}
	
	//方法一：Hierholzer 算法
	Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<String>();
    public List<String> findItinerary1(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }
}
